/**
 * //一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。
 * //
 * //
 * //
 * // 示例 1：
 * //
 * // 输入：nums = [4,1,4,6]
 * //输出：[1,6] 或 [6,1]
 * //
 * //
 * // 示例 2：
 * //
 * // 输入：nums = [1,2,10,4,1,4,3,3]
 * //输出：[2,10] 或 [10,2]
 * //
 * //
 * //
 * // 限制：
 * //
 * //
 * // 2 <= nums.length <= 10000
 * //
 * //
 * //
 * //
 * // Related Topics 位运算 数组 👍 717 👎 0
 */

package com.xixi.basicAlgroithms.bitManipulation;

public class ID_Offer_56_IShuZuZhongShuZiChuXianDeCiShuLcof {
    public static void main(String[] args) {
        Solution solution = new ID_Offer_56_IShuZuZhongShuZiChuXianDeCiShuLcof().new Solution();
    }


    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int[] singleNumbers(int[] nums) {

            //将a和b按异位分到两组
            int res = 0;
            int i = 0;
            //因为 x^x = 0, x^0 = x;所以最后的结果等于a^b
            while (i < nums.length) {
                res ^= nums[i];
                i++;
            }

            //找出异位的分组位，相同的数字都会分到一组
            int div = 1;
            while ((div & res) == 0) {
                div <<= 1;
            }

            //每组按和a、b同位相等的分开，每组求异或值
            //因为 x^x = 0, x^0 = x; 所以每组最后的结果就是a和b
            int a = 0, b = 0;
            for (int n : nums) {
                if ((div & n) != 0) {
                    a ^= n;
                } else {
                    b ^= n;
                }
            }
            return new int[]{a, b};


        }
    }
//leetcode submit region end(Prohibit modification and deletion)


}